/*
 * @lc app=leetcode.cn id=2981 lang=cpp
 *
 * [2981] 找出出现至少三次的最长特殊子字符串 I
 *
 * https://leetcode.cn/problems/find-longest-special-substring-that-occurs-thrice-i/description/
 *
 * algorithms
 * Medium (49.04%)
 * Likes:    3
 * Dislikes: 0
 * Total Accepted:    4K
 * Total Submissions: 8.2K
 * Testcase Example:  '"aaaa"'
 *
 * 给你一个仅由小写英文字母组成的字符串 s 。
 *
 * 如果一个字符串仅由单一字符组成，那么它被称为 特殊 字符串。例如，字符串 "abc" 不是特殊字符串，而字符串 "ddd"、"zz" 和 "f"
 * 是特殊字符串。
 *
 * 返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度，如果不存在出现至少三次的特殊子字符串，则返回 -1 。
 *
 * 子字符串 是字符串中的一个连续 非空 字符序列。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：s = "aaaa"
 * 输出：2
 * 解释：出现三次的最长特殊子字符串是 "aa" ：子字符串 "aaaa"、"aaaa" 和 "aaaa"。
 * 可以证明最大长度是 2 。
 *
 *
 * 示例 2：
 *
 *
 * 输入：s = "abcdef"
 * 输出：-1
 * 解释：不存在出现至少三次的特殊子字符串。因此返回 -1 。
 *
 *
 * 示例 3：
 *
 *
 * 输入：s = "abcaba"
 * 输出：1
 * 解释：出现三次的最长特殊子字符串是 "a" ：子字符串 "abcaba"、"abcaba" 和 "abcaba"。
 * 可以证明最大长度是 1 。
 *
 *
 *
 *
 * 提示：
 *
 *
 * 3 <= s.length <= 50
 * s 仅由小写英文字母组成。
 *
 *
 */
#include <bits/stdc++.h>
using namespace std;
// @lc code=start
class Solution {
public:
    int maximumLength(string s) {
        // 小根堆，留下大的
        priority_queue<int, vector<int>, greater<int>> lens[26];

        int ans = -1;
        for (int i = 0; i < s.size(); i++) {
            int len = 1, idx = s[i] - 'a';
            while (i < s.size() && s[i] == s[i + 1]) {
                i++;
                len++;
            }
            lens[idx].push(len);
            if (lens[idx].size() > 3)
                lens[idx].pop();
        }

        for (auto len : lens) {
            if (len.size() > 0) {
                vector<int> arr(len.size());
                for (int i = arr.size() - 1; i >= 0; i--) {
                    arr[i] = len.top();
                    len.pop();
                }
                ans = max(ans, maxLetterLen(arr));
            }
        }
        return ans;
    }

    int maxLetterLen(vector<int> lens) {
        int res = -1;
        if (lens.size() >= 1) {
            res = max(res, lens[0] - 2);
        }
        if (lens.size() >= 2) {
            res = max(res, min(lens[0] - 1, lens[1]));
        }
        if (lens.size() >= 3) {
            res = max(res, lens[2]);
        }
        return res <= 0 ? -1 : res;
    }
};
// @lc code=end
